#pragma once

#include "base.h"
#include <functional>

OPEN_JLIB_NS


struct List {

  using less_t = std::function<s64(List*, List*)>;

  template<typename T, List T::*M>
  struct iterator {
    inline explicit iterator (List *iter) noexcept : iter(iter) {}
    inline bool operator!= (const iterator &other) const noexcept { return iter != other.iter; }
    inline bool operator== (const iterator &other) const noexcept { return iter == other.iter; }
    inline iterator& operator++ () noexcept { iter = iter->next(); return *this; }
    inline iterator& operator-- () noexcept { iter = iter->prev(); return *this; }
    inline iterator operator++ (int) noexcept { auto old = iter; iter = old->next(); return iterator{old}; }
    inline iterator operator-- (int) noexcept { auto old = iter; iter = old->prev(); return iterator{old}; }
    inline T* operator* () noexcept { return iter->cast(M); }
    inline T* operator-> () noexcept { return iter->cast(M); }
  private:
    List* iter;
  };

  template<typename T, List T::*M>
  struct const_iterator {
    inline explicit const_iterator (const List *iter) noexcept : iter(iter) {}
    inline bool operator!= (const const_iterator &other) const noexcept { return iter != other.iter; }
    inline bool operator== (const const_iterator &other) const noexcept { return iter == other.iter; }
    inline const_iterator& operator++ () noexcept { iter = iter->next(); return *this; }
    inline const_iterator& operator-- () noexcept { iter = iter->prev(); return *this; }
    inline const_iterator operator++ (int) noexcept { auto old = iter; iter = old->next(); return const_iterator{old}; }
    inline const_iterator operator-- (int) noexcept { auto old = iter; iter = old->prev(); return const_iterator{old}; }
    inline const T* operator* () noexcept { return iter->cast(M); }
    inline const T* operator-> () noexcept { return iter->cast(M); }
  private:
    const List* iter;
  };


private:
  inline static void __insert (List *X, List *P, List *N) noexcept {
    X->_prev = P;
    X->_next = N;
    N->_prev = X;
    P->_next = X;
  }

  inline static void __remove (List* X) noexcept {
    X->_next->_prev = X->_prev;
    X->_prev->_next = X->_next;
  }

  inline static void __clear (List* X) noexcept {
    X->_next = X;
    X->_prev = X;
  }
  
  inline static void __shift_right (List* X) noexcept {
    auto P = X->_prev;
    auto N = X->_next;
    if (P == N)
      return;
    P->_next = N;
    N->_prev = P;
    auto NN = N->_next;
    NN->_prev = X;
    X->_prev = N;
    X->_next = NN;
  }
  
  inline static void __shift_left (List* X) noexcept {
    auto P = X->_prev;
    auto N = X->_next;
    if (P == N)
      return;
    N->_prev = P;
    P->_next = N;
    auto PP = P->_prev;
    PP->_next = X;
    X->_next = P;
    X->_prev = PP;
  }

  inline static void __inner_swap (List* X, List* Y) noexcept {
    auto Xn = X->_next;
    auto Xp = X->_prev;
    auto Yn = Y->_next;
    auto Yp = Y->_prev;
    if (Xn == Y) {
      X->_prev = Y;
      Y->_next = X;
    }
    else {
      X->_prev = Yp;
      Y->_next = Xn;
      Xn->_prev = Y;
      Yp->_next = X;
    }
    if (Xp == Y) {
      X->_next = Y;
      Y->_prev = X;
    }
    else {
      X->_next = Yn;
      Y->_prev = Xp;
      Xp->_next = Y;
      Yn->_prev = X;
    }
  }

  inline static void __outer_swap (List* X, List* Y) noexcept {
    auto Xn = X->_next;
    auto Xp = X->_prev;
    auto Yn = Y->_next;
    auto Yp = Y->_prev;
    if (Xn == X) {
      Y->_next = Y;
      Y->_prev = Y;
    }
    else {
      Y->_next = Xn;
      Y->_prev = Xp;
      Xn->_prev = Y;
      Xp->_next = Y;
    }
    if (Yn == Y) {
      X->_next = X;
      X->_prev = X;
    }
    else {
      X->_next = Yn;
      X->_prev = Yp;
      Yn->_prev = X;
      Yp->_next = X;
    }
  }

  inline static List* __bubble_insert (List *node, List *head, List *tail, const less_t &less) {
    for (; head != tail; tail = tail->prev()) {
      if (less(tail, node) <= 0) {
        __insert(node, tail, tail->next());
        return tail;
      }
    }
    __insert(node, head->prev(), head);
    return head->prev();
  }

  inline static void __fast_sort (List* head, List* tail, const less_t &less) {
    if (head == tail)
      return;
    auto base = head;
    auto test = tail;

    if (less(test, base) < 0) {
      __inner_swap(base, test);
      head = test;
      tail = base;
      test = test->_next;
      goto L_backward_with_tail_unsafe;
    }
    else test = test->_prev;

  L_forward_with_head_unsafe:
    if (base == test)
      goto L_recursive;
    if (less(test, base) < 0) {
      __inner_swap(base, test);
      head = test;
      test = test->_next;
      goto L_backward;
    }
    else test = test->_prev;
    goto L_forward_with_head_unsafe;

  L_backward_with_tail_unsafe:
    if (base == test)
      goto L_recursive;
    if (less(base, test) < 0) {
      __inner_swap(test, base);
      tail = test;
      test = test->_prev;
      goto L_forward;
    }
    else test = test->_next;
    goto L_backward_with_tail_unsafe;

  L_forward:
    if (base == test)
      goto L_recursive;
    if (less(test, base) < 0) {
      __inner_swap(base, test);
      test = test->_next;
      goto L_backward;
    }
    else test = test->_prev;
    goto L_forward;

  L_backward:
    if (base == test)
      goto L_recursive;
    if (less(base, test) < 0) {
      __inner_swap(test, base);
      test = test->_prev;
      goto L_forward;
    }
    else test = test->_next;
    goto L_backward;

  L_recursive:
    if (head != base)
      __fast_sort(head, base->_prev, less);
    if (tail != base)
      __fast_sort(base->_next, tail, less);
  }

public:
  inline List () noexcept = default;
  inline List (std::nullptr_t) noexcept : _next(this), _prev(this) {}
  inline List (List *P, List *N) noexcept { __insert(this, P, N); }

  inline bool only () const noexcept { return this == _next; }
  inline bool pair () const noexcept { return _next == _prev && _next == this; }

  inline List* next () noexcept { return _next; }
  inline List* prev () noexcept { return _prev; }

  inline const List* next () const noexcept { return _next; }
  inline const List* prev () const noexcept { return _prev; }

  inline void push_back (List* X) noexcept { __insert(X, _prev, this); }
  inline void push_front (List* X) noexcept { __insert(X, this, _next); }

  inline void pop_back () noexcept { _prev->detach(); }
  inline void pop_front () noexcept { _next->detach(); }
  
  inline void shift_right () noexcept { __shift_right(this); }
  inline void shift_left () noexcept { __shift_left(this); }

  inline void clear () noexcept { __clear(this); }
  inline void detach () noexcept { __remove(this); __clear(this); }

  inline void replace (List* X) noexcept { __outer_swap(this, X); }
  inline void swap (List* X) noexcept { __inner_swap(this, X); }
  inline bool bubble_insert (List *node, const less_t &less) noexcept { return __bubble_insert(node, _next, _prev, less) == _prev; }
  inline void fast_sort (const less_t &less) { __fast_sort(_next, _prev, less); }

  template<typename T>
  inline T* cast (List T::*member) noexcept {
    T* st = nullptr;
    return (T*)((unsigned long)this - (unsigned long)&(st->*member));
  }
  template<typename T>
  inline const T* cast (List T::*member) const noexcept {
    T* st = nullptr;
    return (const T*)((unsigned long)this - (unsigned long)&(st->*member));
  }

  inline static void fast_sort (List *head, List *tail, const less_t& less) { __fast_sort(head, tail, less); }

private:
  List* _next;
  List* _prev;
};


CLOSE_JLIB_NS
